1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <cstdio>
#include <algorithm>
#define LL long long
const int maxn = 2e5 + 5;
using namespace std;
int n, Q, a[maxn], b[maxn], cnt[maxn];
struct T{
struct A{
int l, r;
LL v, vi;
}a[maxn << 2];
void build(int cur, int l, int r){
a[cur].l = l, a[cur].r = r;
if (l == r){
a[cur].v = cnt[l];
a[cur].vi = a[cur].v * (l - 1);
return;
} int mid = l + r >> 1;
build(cur << 1, l, mid); build(cur << 1 | 1, mid + 1, r);
a[cur].v = a[cur << 1].v + a[cur << 1 | 1].v;
a[cur].vi = a[cur << 1].vi + a[cur << 1 | 1].vi;
}
void upd(int cur, int p, int k){
if (a[cur].l == a[cur].r){
a[cur].v += k;
a[cur].vi += k * (p - 1);
return;
} int mid = a[cur].l + a[cur].r >> 1;
if (p <= mid) upd(cur << 1, p, k);
else upd(cur << 1 | 1, p, k);
a[cur].v = a[cur << 1].v + a[cur << 1 | 1].v;
a[cur].vi = a[cur << 1].vi + a[cur << 1 | 1].vi;
}
LL QueryV(int cur, int l, int r){
if (a[cur].l > r || a[cur].r < l) return 0;
if (a[cur].l >= l && a[cur].r <= r) return a[cur].v;
return QueryV(cur << 1, l, r) + QueryV(cur << 1 | 1, l, r);
}
LL QueryVI(int cur, int l, int r){
if (a[cur].l > r || a[cur].r < l) return 0;
if (a[cur].l >= l && a[cur].r <= r) return a[cur].vi;
return QueryVI(cur << 1, l, r) + QueryVI(cur << 1 | 1, l, r);
}
}t1, t2; LL sum = 0;
int main(){
scanf("%d%d", &n, &Q);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
t1.build(1, 1, n);
for (int i = 1; i <= n; i++){
t1.upd(1, a[i], 1); b[i] = t1.QueryV(1, a[i] + 1, n);
cnt[b[i] + 1]++; sum += b[i];
} t2.build(1, 1, n);
while (Q--){
int opt, x; scanf("%d%d", &opt, &x);
if (opt == 1){
if (a[x + 1] > a[x]){
t2.upd(1, b[x] + 1 + 1, 1), t2.upd(1, b[x] + 1, -1);
b[x]++, sum++;
}
else{
t2.upd(1, b[x + 1] - 1 + 1, 1), t2.upd(1, b[x + 1] + 1, -1);
b[x + 1]--, sum--;
}
swap(a[x], a[x + 1]); swap(b[x], b[x + 1]);
}
if (opt == 2) printf("%lld\n", sum - t2.QueryVI(1, 1, x + 1) - x * t2.QueryV(1, x + 2, n));
}
return 0;
}
|